#define _BSD_SOURCE    // usleep is from BSD

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdbool.h>

/**
 * the output strings MUST be of the form:
 * (t=TIME) WHALE_ID: ACTION
 * 
 * with NO leading or trailing spaces
 * 
 * TIME - the value of elapsed_time()
 * WHALE_ID - the id passed into Male(int id) and Female(int id)
 * ACTION - one of the followoing exact phrases (with no leading
 *                    or trailing spaces):
 *
 *    Male Created
 *    Female Created
 *    Found Mate
 *    Became MatchMaker
 *    Mated
 *
 */

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
int pthread_mutex_init(pthread_mutex_t *restrict mutex,
                       const pthread_mutexattr_t *restrict attr);

//It increments the value of the semaphore and wakes up a blocked process waiting on the semaphore, if any. 
int sem_post(sem_t *sem);
//gets the current value of sem and places it in the location pointed to by valp
int sem_getvalue(sem_t *sem, int *valp);
//If the value of the semaphore is negative, the calling process blocks; one of the blocked processes wakes up when another process calls sem_post.
int sem_wait(sem_t *sem);
sem_t semaphore;
 
static pthread_mutex_t stdout_lock;

#define LOCKED_PRINTF(fmt, args...) \
    pthread_mutex_lock(&stdout_lock); \
    printf(fmt, args); \
    fflush(stdout); \
    pthread_mutex_unlock(&stdout_lock)

static struct timeval time0;

sem_t search_mutex;

typedef enum {
    INVALID,
    MATCHMAKER,
    MATCHED,
    WAITING_FOR_MATE,
    DEAD
} whale_state_t;

typedef enum {
    MALE,
    FEMALE
} gender_t;

typedef struct{
    int id;
    int partner;
    gender_t gender;
    whale_state_t state;
} whale_info_t;

int num_whales;

whale_info_t **whales;



double elapsed_time() {
    struct timeval tv;
    gettimeofday(&tv, NULL);

    return (tv.tv_sec - time0.tv_sec + (tv.tv_usec - time0.tv_usec) / 1.e6 );
}

void initialize_whale(gender_t gender, int id){
    if(whales[id] != NULL){
        LOCKED_PRINTF("    whale %d already exists\n", id);
        pthread_exit(NULL);
    }    
    whales[id] = malloc(sizeof(whale_info_t));
    whales[id]->partner = -1;
    whales[id]->id = id;
    whales[id]->gender = gender;
    whales[id]->state = INVALID;
}

#define CHECKPTR(x)                                                     \
    do {                                                                \
        if ((x) == NULL) {                                              \
            LOCKED_PRINTF("%s %s\n","null pointer in", __FUNCTION__);   \
        }                                                               \
    }while(0)

void look_for_mate(int id){
    CHECKPTR(whales[id]);
    if(whales[id]->partner != -1){
        return;
    }
    for(int i = 0; i < num_whales; i+=1){
        whale_info_t *other = whales[i];
        if((other != NULL) && (other->gender != whales[id]->gender) && (other->partner == -1)){
            
            whales[id]->partner = i;
            whales[i]->partner = id;
            LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), id, "Found Mate");
            LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), whales[id]->partner, "Found Mate");
            return;
        }   
    }
}

whale_info_t *find_pair()
{
    //must be locked
    for(int i = 0; i < num_whales; i++){
        if((whales[i] != NULL) && (whales[i]->partner != -1) && whales[i]->state == WAITING_FOR_MATE && whales[whales[i]->partner] != NULL && whales[whales[i]->partner]->state == WAITING_FOR_MATE){
            whales[i]->state = MATCHED;
            whales[whales[i]->partner]->state = MATCHED;
            return whales[i];
        }
    }
    return NULL;
    //later
}

void decide_action(int id) {
    while(true){
        whale_info_t *found_match = NULL;
        sem_wait(&search_mutex);
        //LOCKED_PRINTF("%s", "wait before Matchmaker\n");
        if (found_match = find_pair()) {
            whales[id]->state = MATCHMAKER;
            LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), id, "Became Matchmaker");
        }
        else {
            whales[id]->state = WAITING_FOR_MATE;
        }
        sem_post(&search_mutex);
        if(found_match != NULL){
            //LOCKED_PRINTF("Working on pair %d,%d\n", found_match->id, found_match->partner);
            if (whales[id]->state != MATCHMAKER) {
                LOCKED_PRINTF("%s", "impossible\n");
                goto THREAD_QUIT;
            }
            int first = found_match->id;
            int second = found_match->partner;
            CHECKPTR(whales[first]);
            CHECKPTR(whales[second]);
            if(first != whales[second]->partner){
                LOCKED_PRINTF("    invalid operation, non-matching pair (%d,%d) vs (%d,%d)", first, second,  whales[second]->id, whales[second]->partner);
                goto THREAD_QUIT;
            }
            LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), first, "Mated");
            LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), second, "Mated");
            //free(whales[first]);
            //free(whales[second]);
            whales[first]->state = DEAD;
            whales[second]->state = DEAD;
            continue;
        }
        else{
            if (whales[id]->state == DEAD) {
                goto THREAD_QUIT;
            }
            if (whales[id] == NULL) {
                goto THREAD_QUIT;
            }
            if (whales[id]->state == MATCHMAKER) {
                LOCKED_PRINTF("%s", "ERROR\n");
                goto THREAD_QUIT;
            }
            
            //look for a mate
            while(true){
                sem_wait(&search_mutex);
                look_for_mate(id);
                sem_post(&search_mutex);
                if(whales[id] == NULL || whales[id]->partner != -1){
                    pthread_exit(NULL);
                }
            }
            break;
        }
    }
    // LOCKED_PRINTF("thread %d about to exit \n", id);
THREAD_QUIT:
    pthread_exit(NULL);
}



void *create_whale(void* arg) {
    int id = *((int *) arg);
    gender_t gender;
    // is this a male or a female?
    if (rand() & 1) { // odd for male
        gender = MALE;
        LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), id, "Male Created");
//create_male(id);
    } else { // even for female
        gender = FEMALE;
        LOCKED_PRINTF("(t=%f) %d: %s\n", elapsed_time(), id, "Female Created");
    }
    //this must be locked
    sem_wait(&search_mutex);
    initialize_whale(gender,id);
    sem_post(&search_mutex);
    //LOCKED_PRINTF("%s", "create whale before decide_action\n");
    decide_action(id);
    //after we initialize 
    //pthread_exit(NULL);
}

void whale_sleep(int wait_time_ms) {
    usleep(wait_time_ms * 1000); // convert from ms to us
}

void usage(char *arg0) {
    fprintf(stderr, "Usage: %s num_whales wait_time\n"
                    "\tnum_whales - the total number of whales to create\n"
                     "\twait_time - the amount of time to wait before creating another whale (seconds)\n",
                    arg0);
    exit(-1);
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        usage(argv[0]);
    }
    
    pthread_mutex_init(&stdout_lock, NULL);
    
    // seed the random number generator
    struct timeval tv;
    gettimeofday(&tv, NULL);
    srand(tv.tv_usec);

    gettimeofday(&time0, NULL);

    num_whales = atoi(argv[1]);
    int wait_time_ms = atof(argv[2]) * 1000;
    whales = malloc(sizeof(whale_info_t*) * num_whales);
    for(int i = 0; i < num_whales; i+=1){
        whales[i] = NULL;
    }
    sem_init(&search_mutex, 0, 1);
    pthread_attr_t thread_attr;
    pthread_attr_init(&thread_attr);
    pthread_attr_setdetachstate(&thread_attr, PTHREAD_CREATE_DETACHED);

    for (int i = 0; i < num_whales; i+=1) {
        whale_sleep(wait_time_ms);
        pthread_t whale_thread_id;
        pthread_create(&whale_thread_id, &thread_attr, create_whale, (void *) &i);
    }

    // this should enough time to resolve the matches
    // than can be resolved
//    LOCKED_PRINTF("%s", "resolving matches before exiting \n");
    //safeguard against infinite loop
    int count = 0;
    while(count++ < 100){
        bool male_found = false; 
        bool female_found = false;
        bool mm_found = false;
        for(int i = 0; i < num_whales; i+=1){
            if(whales[i] == NULL){
                continue;
            }
            if(whales[i]->gender == FEMALE){
                female_found = true;
                continue;
            }
            else if(whales[i]->gender == MALE){
                male_found = true;
                continue;
            }
            if ((male_found == true) && (female_found == true) && (whales[i]->state==MATCHMAKER)){
            }
            else{
            whale_sleep(wait_time_ms * 10.0);
            break;
        }
        }
        
    }
    pthread_mutex_destroy(&stdout_lock);
}
